package ch6;

import lombok.Data;

import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;

@Data
public class BinaryTreeNode<T extends Comparable> {

    private T data;

    private BinaryTreeNode left;

    private BinaryTreeNode right;

    /**
     * 递归先序遍历
     * @param root
     */
    public void preOrder(BinaryTreeNode root){
        if (root != null) {
            System.out.println("root.getData() = " + root.getData());
            preOrder(root.getLeft());
            preOrder(root.getRight());
        }
    }


    /**
     * 中序遍历 时间复杂度O(n) ,空间复杂度O(n)
     * @param root
     */
    public void inOrder(BinaryTreeNode root){
        if (root != null) {
            inOrder(root.getLeft());
            System.out.println("root.getData() = " + root.getData());
            inOrder(root.getRight());
        }
    }

    /**
     * 后序遍历
     * @param root
     */
    public void postOrder(BinaryTreeNode root){
        if (root != null) {
            postOrder(root.getLeft());
            postOrder(root.getRight());
            System.out.println("root.getData() = " + root.getData());
        }
    }


    /**
     * 层次遍历
     * 时间复杂度O(n) ,空间复杂度O(n)
     * @param root
     */
    public void levelOrder(BinaryTreeNode root){
        BinaryTreeNode temp;

        Queue queue = new LinkedList<>();

        if (root == null) {
            return;
        }
        queue.add(root);
        while (!queue.isEmpty()) {
                temp = (BinaryTreeNode) queue.poll();
            System.out.println("temp.getData() = " + temp.getData());
            if (temp.getLeft() != null) {
                queue.add(temp.getLeft());
            }

            if (temp.getRight() != null) {
                queue.add(getRight());
            }
        }
        queue.clear();
    }

    /**
     * 获取节点个数
     * @param root
     * @return
     */
    public int getSizeOfNode(BinaryTreeNode root){
        if (root != null) {
            return getSizeOfNode(root.getRight()) + 1 + getSizeOfNode(root.getLeft());
        }
        return 0;
    }

    /**
     * 查找
     * @param root
     * @param data
     * @return
     */
    public boolean findInTree(BinaryTreeNode root, T data){

        if (root == null) {
            return false;
        }

        if (data.equals(root.getData())) {
            return true;
        }else {
            boolean res = findInTree(root.getLeft(), data);
            if (!res) {
                return findInTree(root.getRight(),data);
            }
        }

        return false;
    }

    /**
     * 查找最大值
     * @param root
     * @return
     */
    public T findMax(BinaryTreeNode root){
        T root_val;
        T left;
        T right;
        T max = null;

        if (root != null) {
            max = (T) root.getData();
        }

        if (root != null) {
            root_val = (T) root.getData();
            left = findMax(root.getLeft());
            right = findMax(root.getRight());

            if (left != null && right != null) {
                if (left.compareTo(right) > 0) {
                    max = left;
                }else {
                    max = right;
                }
            }

            if (max != null) {
                if (root_val.compareTo(max) > 0) {
                    max = root_val;
                }
            }
        }
        return max;
    }


    /**
     * 逆向逐层输出树中的元素
     * @param root
     */
    public void levelOrderTraverInReverse(BinaryTreeNode root){

        Queue queue = new LinkedList<>();
        Stack<BinaryTreeNode> stack = new Stack<>();

        BinaryTreeNode temp;

        if (root == null) {
            return;
        }

        queue.add(root);

        while (!queue.isEmpty()) {
            temp = (BinaryTreeNode) queue.poll();
            if (temp.getRight() != null) {
                queue.add(temp.getRight());

            }

            if (temp.getLeft() != null) {
                queue.add(temp.getLeft());
            }

            stack.push(temp);
        }

        while (!stack.isEmpty()) {
            System.out.println("stack.pop().getData() = " + stack.pop().getData());
        }
    }


    /**
     * 求树高度
     * @return
     */
    public int getHightOfTree(BinaryTreeNode root){
        int leftH, rightH;

        if (root != null) {
            leftH =  getHightOfTree(root.getLeft());
            rightH = getHightOfTree(root.getRight());

            if (leftH >= rightH) {
                return leftH + 1;
            }else {
                return rightH + 1;
            }
        }
        return 0;
    }

    /**
     * 获取最深节点
     * @param root
     * @return
     */
    public BinaryTreeNode getDeepestNode(BinaryTreeNode root){

        if (root != null) {
            BinaryTreeNode temp = null;
            Queue queue = new LinkedList<>();

            queue.add(root);

            while (! queue.isEmpty()) {
                temp = (BinaryTreeNode) queue.poll();

                if (temp.getLeft() != null) {
                    queue.add(temp.getLeft());
                }

                if (temp.getRight() != null) {
                    queue.add(temp.getRight());
                }

            }

            queue.poll();

            return temp;
        }

        return null;
    }
}
